//76 最小覆盖子串
//给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。 
//
// 示例： 
//
// 输入: S = "ADOBECODEBANC", T = "ABC"
//输出: "BANC" 
//
// 说明： 
//
// 
// 如果 S 中不存这样的子串，则返回空字符串 ""。 
// 如果 S 中存在这样的子串，我们保证它是唯一的答案。 
// 
// Related Topics 哈希表 双指针 字符串 Sliding Window


package leetcode.editor.cn;

public class A76MinimumWindowSubstring {
    public static void main(String[] args) {
        Solution solution = new A76MinimumWindowSubstring().new Solution();
        System.out.println("佛祖保佑");
        System.out.println("\uD80C\uDC09\uD80C\uDC02\uD80C\uDC03\uD80C\uDC10");

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String minWindow(String s, String t) {
            char[] ss = s.toCharArray();
            int charNum = 256;

            int[] words = new int[charNum];
            for (int i = 0; i < t.length(); i++) {
                words[t.charAt(i)]++;
            }


            int[] curr = new int[charNum];
            boolean[] b = new boolean[charNum];// 用于迅速找到该字符是否匹配
            int matchCount = 0;//matchCount == charNum 时说明匹配
            for (int i = 0; i < charNum; i++) {
                if (words[i] == 0) {
                    b[i] = true;
                    matchCount++;
                }
            }

            int left = 0;
            int right = 0;

            int minCount = Integer.MAX_VALUE;
            String ans = "";
            while (right < ss.length || (matchCount == charNum && left < ss.length)) {
                if (matchCount == charNum) {//左指针右移，以便寻求新的更短
                    int index = ss[left];
                    curr[index]--;
                    if (b[index] && curr[index] < words[index]) {// 由匹配转为不匹配
                        matchCount--;
                        b[index] = false;
                    }
                    left++;
                } else {// 右指针右移，以找到满足结果
                    int index = ss[right];
                    curr[index]++;
                    if (!b[index] && curr[index] == words[index]) {// 不匹配转为匹配
                        matchCount++;
                        b[index] = true;
                    }
                    right++;
                }

                // 更新答案
                if (matchCount == charNum && right - left < minCount) {
                    minCount = right - left;
                    ans = s.substring(left, right);
                }
            }

            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
